package LintCode;

/**
 * @Classname BinarySearch
 * @Description TODO
 * @Date 2021/3/4 16:26
 * @Created by ASUS
 */
public class BinarySearch {
    /**
     * @param nums:   An integer array sorted in ascending order
     * @param target: An integer
     * @return: An integer
     */
    public int findPosition(int[] nums, int target) {
        // write your code here
        if (nums == null || nums.length == 0) return -1;
        if (target < nums[0] || target > nums[nums.length - 1]) return -1;
        if (nums[0] == target) return 0;
        if (nums[nums.length - 1] == target) return nums.length - 1;
        int index = nums.length >> 1, start = 0, end = nums.length - 1;
        while (start < end - 1) {
            if (nums[index] == target) return index;
            else if (nums[index] < target) start = index;
            else end = index;
            index = (start + end) >> 1;
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(new BinarySearch().findPosition(new int[]{1, 2, 3, 4, 5, 6, 88, 99}, 5));
    }
}
